package model;

import java.awt.*;
import java.util.*;


public class RoffTriangleManager {

    private RoffVector3D[] pointArray;
    private int[] pointXArray;
    private int[] pointYArray;
    private int[] depthOrder;
    private RoffTriangle[] triangles;

    private int numTriangles;

    public RoffTriangleManager() {
        numTriangles = 0;
    }

    public void setPointArray(RoffVector3D[] newPointArray) {
        pointArray = newPointArray;
    }

    public void set2DPointArrays(int[] newPointXArray, int[] newPointYArray) {
        pointXArray = newPointXArray;
        pointYArray = newPointYArray;
    }
    public void generateTrangles(GeometryModel3D g){
    	tessellate(g.polygons); 
    }
    public void tessellate(RoffPolygon3D[] polyArray) {
        int i;
        int numPoints;
        RoffVector3D centroid;
        ArrayList tempTriangles = new ArrayList();
        triangles = null;
        numTriangles = 0;

        // Build the triangle list from the polygons in polyArray;
        int numPolys = 0;
        if (polyArray != null) {
            numPolys = polyArray.length;
        }
        for (i = 0;i < numPolys;i++) {
            //Find out how big the polygon is and set variables
            // accordingly.
            numPoints = polyArray[i].getNumEdges();
            // If we already have a triangle, just add it.
            if (numPoints == 3) {
                tempTriangles.add(new RoffTriangle(polyArray[i].getVertex(0),
		                                   polyArray[i].getVertex(1),
					           polyArray[i].getVertex(2),
					           pointArray)
                                  );
                numTriangles++;
            } else {
                // Find the centroid of the polgon.
                centroid = pointArray[polyArray[i].getVertex(0)];
                int j;
                for (j = 1;j < numPoints;j++) {
                    centroid = centroid.add(pointArray[polyArray[i].getVertex(j)]);
                }
                centroid = centroid.scalarDivide(numPoints);

                // Find the index of the point in the polygon closest to
                // the centroid.
                int indexClosest = 0;
                double distance;
                double minDistance = ((pointArray[polyArray[i].getVertex(indexClosest)]).sub(centroid)).getSquaredLength();
                for (j = 1;j < numPoints;j++) {
                    distance = ((pointArray[polyArray[i].getVertex(j)]).sub(centroid)).getSquaredLength();
                    if (distance < minDistance) {
                        minDistance = distance;
                        indexClosest = j;
                    }
                }

                // Starting at that point, move around the polygon,
                // tearing off triangles.
                int secondPoint;
                int thirdPoint;
                for (j = 0; j < (numPoints - 2); j++) {
                    secondPoint = indexClosest + j + 1;
                    if (secondPoint >= numPoints) {
                        secondPoint = secondPoint - numPoints;
                    }
                    thirdPoint = indexClosest + j + 2;
                    if (thirdPoint >= numPoints) {
                        thirdPoint = thirdPoint - numPoints;
                    }
                    tempTriangles.add(new RoffTriangle(polyArray[i].getVertex(indexClosest),
		                                           polyArray[i].getVertex(secondPoint),
		                                       polyArray[i].getVertex(thirdPoint),
                                                       pointArray)
                                     );
                    numTriangles++;
                }
            }
        }
        if (numTriangles > 0) {
            triangles = new RoffTriangle[numTriangles];
            depthOrder = new int[numTriangles];

            // Set an initial order that can be sorted once a From point
            // is picked and load the triangles into the array from the
            // dynamically sized ArrayList.
            for (i = 0;i < numTriangles;i++) {
                triangles[i]  = (RoffTriangle)tempTriangles.get(i);
                depthOrder[i] = i;
            }
        }
        tempTriangles.clear();
        tempTriangles = null;
    }

    public void orderTriangles(RoffVector3D fromPoint, RoffVector3D atPoint) {

        RoffVector3D LoS = atPoint.sub(fromPoint);
        LoS.normalize();
        int i;
        // Adjust all the triangles to have the correct depth for
        // the given from point.
        for (i = 0;i < numTriangles;i++) {
            triangles[i].updateView(fromPoint, LoS);
        }

        // Sort depthOrder on the basis of triangles[index]->closer()
        // and triangles[index]->sameDepth().
        // Build a heap
        int heapsize = numTriangles;
        for (i = ((heapsize - 1) / 2); i >= 0; i --) {
            Heapify(i, heapsize);
        }

        // Sort from the heap.
        int tempIndex;
        for (i = numTriangles - 1; i > 0; i --) {
            tempIndex = depthOrder[0];
            depthOrder[0] = depthOrder[i];
            depthOrder[i] = tempIndex;
            heapsize --;
            Heapify(0, heapsize);
        }
    }

    public void rebuild() {
        for (int i = 0;i < numTriangles;i++) {
            (triangles[i]).rebuild();
        }
    }

    public RoffTriangle get(int triangleIndex) {
        return triangles[depthOrder[triangleIndex]];
    }

    public Polygon getPolygon(int triangleIndex) {

        RoffTriangle tri = triangles[depthOrder[triangleIndex]];

        int[] xs = new int[3];
        int[] ys = new int[3];

        xs[0] = pointXArray[tri.getP1()];
        ys[0] = pointYArray[tri.getP1()];
        xs[1] = pointXArray[tri.getP2()];
        ys[1] = pointYArray[tri.getP2()];
        xs[2] = pointXArray[tri.getP3()];
        ys[2] = pointYArray[tri.getP3()];

        return new Polygon(xs, ys, 3);
    }

    public int getNumberOfTriangles() {
        return numTriangles;
    }

    private void Heapify(int index, int heapsize) {

        // All children of the element passed are located at
        // (index * 2) + offset, where 0 < offset <= 2.
        int nodeBase = index * 2;

        // Assume that the given element is already the largest and
        // that there is no child larger.
        int largestIndex = index;

        // Check the left child, if it is in the heap, and pick it
        // if it is larger.
        if (nodeBase + 1 < heapsize) {
            if (!(triangles[depthOrder[largestIndex]].closer(triangles[depthOrder[nodeBase + 1]]))) {
                largestIndex = nodeBase + 1;
            }
        }

        // Check the right child, if it is in the heap, and pick it
        // if it is larger.
        if (nodeBase + 2 < heapsize) {
            if (!(triangles[depthOrder[largestIndex]].closer(triangles[depthOrder[nodeBase + 2]]))) {
                largestIndex = nodeBase + 2;
            }
        }

        // If one of the children was larger, swap it with the parent and
        // call Heapify again to see if the parent should move down further.
        if ( largestIndex != index ) {
	    int temp = depthOrder[index];
            depthOrder[index] = depthOrder[largestIndex];
            depthOrder[largestIndex] = temp;
            Heapify(largestIndex, heapsize);
        }
    }
}
